#include <iostream>
#include <cassert>

using namespace std;

// Quick Find
namespace UF1{
	class UnionFind{
		private:
			int *id;			// id 的数组
			int count;			// 一共多少个元素
		public:
			UnionFind(int n){
				count = n;
				id = new int[n];
				// 初始情况每个元素是个独立的组
				for(int i = 0; i < n; ++i){
					id[i] = i;
				}
			}

			~UnionFind(){
				delete[] id;		// 释放id数组
			}

			// O(1) 直接访问id值
			int find(int p){
				assert(p >= 0 && p < count);
				return id[p];
			}

			// 判断两个元素是否连接在一起
			bool isConnected(int p, int q){
				return find(p) == find(q);
			}

			// Union 并时间复杂度 O(n)
			void unionElements(int p, int q){
			
				int pID = find(p);
				int qID = find(q);

				// 两个元素已经在一起了
				if(pID == qID){
					return;
				}

				for(int i = 0; i < count; ++i){
					if(id[i] == pID){
						id[i] = qID;		// 将q 的id 号赋值给 p
					}
				}
			}
	};
}
